"""
题目：判断一棵二叉树是否是对称的（即镜像对称，左右子树互为镜像）。
"""


class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


"""
这种递归写法是精准的对称对比递归,每一层递归都聚焦于 “对称位置的两个节点”，且也不会导致二叉树的部分区域被重复判断。
"""
def is_symmetric(root):
    """判断二叉树是否对称"""
    if not root:  # 空树是对称的
        return True
    def is_mirror(left, right):
        # 左右节点都为空，对称
        if not left and not right:
            return True
        # 一个为空一个不为空，不对称;
        # 双False的情况，在上面if中已经进去并返回了。
        #如果是双True,则不进入该if，继续往下走
        #一个T，一个F，则进入 return False
        if not left or not right:
            return False
        # 节点值不同，不对称
        if left.val != right.val:
            return False
        # 递归判断：左节点的左子树与右节点的右子树是否对称，
        # 且左节点的右子树与右节点的左子树是否对称
        return is_mirror(left.left, right.right) and is_mirror(left.right, right.left)
    # 检查根节点的左右子树是否镜像对称
    return is_mirror(root.left, root.right)


# 辅助函数：创建二叉树（复用）
def create_binary_tree(arr):
    if not arr:
        return None
    root = TreeNode(arr[0])
    queue = [root]
    index = 1
    while queue and index < len(arr):
        current = queue.pop(0)
        if arr[index] is not None:
            current.left = TreeNode(arr[index])
            queue.append(current.left)
        index += 1
        if index < len(arr) and arr[index] is not None:
            current.right = TreeNode(arr[index])
            queue.append(current.right)
        index += 1
    return root


# 测试
# 对称树
root1 = create_binary_tree([1, 2, 2, 3, 4, 4, 3])
print(is_symmetric(root1))  # 输出: True

# 不对称树
root2 = create_binary_tree([1, 2, 2, None, 3, None, 3])
print(is_symmetric(root2))  # 输出: False
